Search results for " Permuted strings"

showing 3 items of 3 documents

ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS

2011

The Parikh vector p(s) of a string s is defined as the vector of multiplicities of the characters. Parikh vector q occurs in s if s has a substring t with p(t)=q. We present two novel algorithms for searching for a query q in a text s. One solves the decision problem over a binary text in constant time, using a linear size index of the text. The second algorithm, for a general finite alphabet, finds all occurrences of a given Parikh vector q and has sub-linear expected time complexity; we present two variants, which both use a linear size index of the text.

FOS: Computer and information sciencesJ.3average case analysis.Binary numberaverage case analysispermuted stringpermuted stringsComputer Science - Data Structures and AlgorithmsComputer Science (miscellaneous)Parikh vectorData Structures and Algorithms (cs.DS)Pattern matchingTime complexityMathematicsString (computer science)Parikh vectorsstring algorithmDecision problemstring algorithmsSubstringParikh vectors; permuted strings; pattern matching; string algorithms; average case analysisF.2.2; J.3Index (publishing)pattern matchingF.2.2Constant (mathematics)AlgorithmComputer Science::Formal Languages and Automata Theory
researchProduct

Searching for Jumbled Patterns in Strings

2009

Parikh vectors permuted strings pattern matching string algorithms average case analysisString algorithmsAverage case analysis; Parikh vectors; Pattern matching; Permuted strings; String algorithmsPermuted stringsParikh vectorsAverage case analysisPattern matching
researchProduct

On Approximate Jumbled Pattern Matching in Strings

2011

Given a string s, the Parikh vector of s, denoted p(s), counts the multiplicity of each character in s. Searching for a match of a Parikh vector q in the text s requires finding a substring t of s with p(t) = q. This can be viewed as the task of finding a jumbled (permuted) version of a query pattern, hence the term Jumbled Pattern Matching. We present several algorithms for the approximate version of the problem: Given a string s and two Parikh vectors u, v (the query bounds), find all maximal occurrences in s of some Parikh vector q such that u <= q <= v. This definition encompasses several natural versions of approximate Parikh vector search. We present an algorithm solving this problem …

Parikh vectors: Average case analysiApproximate searchString algorithmsDiscrete mathematicsWeight functionanalysisSearch engine indexingParikh vectorsAverage case analysisApproximate string matchingSubstringString algorithmTheoretical Computer ScienceCombinatoricsComputational Theory and MathematicsString algorithms Pattern matching Parikh vectors Average case analysis Approximate search Permuted stringsPermuted stringsAverage caseTheory of computationWavelet TreePreprocessorPattern matchingPattern matchingMathematicsTheory of Computing Systems
researchProduct